package main.leetcode.clockin.April;

/**
 * 72.编辑距离
 *
 * <p>给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 *
 * <p>你可以对一个单词进行如下三种操作：
 *
 * <p>插入一个字符 删除一个字符 替换一个字符
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/edit-distance
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day6 {
    public static void main(String[] args) {
        System.out.println(new day6().minDistance("horse", ""));
    }

    // 动态规划——自底向上
    public int minDistanceBU(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // dp[i][j]表示word[0..i-1]到word[0..j-1]需要经历的最少变换次数
        int[][] dp = new int[m + 1][n + 1];

        // 初始化
        int i, j;
        // 当word2为空时，将word1逐个删除的次数
        for (i = 0; i <= m; ++i) {
            dp[i][0] = i;
        }
        // 当word1为空时，将word2逐个删除的次数
        for (j = 0; j <= n; ++j) {
            dp[0][j] = j;
        }

        for (i = 1; i <= m; ++i) {
            for (j = 1; j <= n; ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 如果两个字符相同，则不用变换
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 如果两个字符不同，则选取以下三种中的最小值并+1，表示当前位置字符的变换
                    dp[i][j] =
                            Math.min(
                                            Math.min(
                                                    dp[i][j - 1], // 插入字符
                                                    dp[i - 1][j]), // 删除字符
                                            dp[i - 1][j - 1]) // 替换字符
                                    + 1;
                }
            }
        }
        return dp[m][n];
    }

    // 动态规划——自顶向下
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        return getDistance(word1, word2, dp, m, n);
    }

    private int getDistance(String word1, String word2, int[][] dp, int m, int n) {
        if (m == 0) return n;
        if (n == 0) return m;
        if (dp[m][n] > 0) return dp[m][n];
        if (word1.charAt(m - 1) == word2.charAt(n - 1)) {
            return dp[m][n] = getDistance(word1, word2, dp, m - 1, n - 1);
        } else {
            return dp[m][n] =
                    Math.min(
                                    Math.min(
                                            getDistance(word1, word2, dp, m, n - 1),
                                            getDistance(word1, word2, dp, m - 1, n)),
                                    getDistance(word1, word2, dp, m - 1, n - 1))
                            + 1;
        }
    }
}
